import heapq

def dij(s):
    q=[]
    dis[s]=0
    heapq.heappush(q,(0,s)) # （距离，节点）

    while q:
        cnt,u=heapq.heappop(q)
        if cnt!=dis[u]:
            continue

        for v,w in mp[u]:
            if dis[u]+w<dis[v]:
                dis[v]=dis[u]+w
                heapq.heappush(q,(dis[v],v))

INF=float('inf')
n,m=map(int,input().split())

# 邻接表
mp=[[] for _ in range(n+1)]
# 节点的最短距离
dis=[INF]*(n+1)

# 邻接表存储节点信息
for _ in range(m):
    a,b,w=map(int,input().split())
    mp[a].append((b,w))

dij(1)

for i in range(1,n+1):
    if dis[i]==INF:
        print(-1,end=' ')
    else:
        print(dis[i],end=' ')
